//import java.util.ArrayList;
//
//public class Solution {
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        System.out.println(solution.VerifySquenceOfBST(new int[]{4,6,7,5}));
//        ArrayList<Integer> list = new ArrayList<>();
//        list.add(12);
//
//    }
//    public boolean VerifySquenceOfBST(int [] sequence) {
//        if (sequence == null || sequence.length == 0) {
//            return false;
//        }
//        return VerifySquenceOfBSTHelper(sequence,0,sequence.length - 1);
//    }
//    public boolean VerifySquenceOfBSTHelper(int[] sequence,int start,int end) {
//        if (start >= end) {
//            return true;
//        }
//        int i = start;
//
//        int root = sequence[end];
//
//        while (i <= end && sequence[i] <= root) {
//            i++;
//        }
//        for (int j = i;j <= end ;j++) {
//            if (sequence[j] < root) {
//                return false;
//            }
//        }
//        return VerifySquenceOfBSTHelper(sequence,start,i-1) &&
//                VerifySquenceOfBSTHelper(sequence,i,end-1);
//    }
//}

import java.util.ArrayList;

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
 }


public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        ArrayList<Integer> list = new ArrayList<>();
        func(root,expectNumber,result,list);

        return result;
    }
    public  void func(TreeNode root,int  expectNumber,ArrayList<ArrayList<Integer>> result,ArrayList<Integer> list){
        if (root == null) {
            return;
        }
        list.add(root.val);
        expectNumber -= root.val;
        if (expectNumber == 0 && root.left == null && root.right == null) {
            result.add(list);
        }
        func(root.left,expectNumber,result,list);
        func(root.right,expectNumber,result,list);

        list.remove(list.size() - 1);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        TreeNode B = new TreeNode(5);
        TreeNode C = new TreeNode(12);
        TreeNode D = new TreeNode(4);
        TreeNode E = new TreeNode(7);
        root.left = B;
        root.right = C;
        B.left = D;
        B.right = E;

        Solution solution = new Solution();
        solution.FindPath(root,22);
        System.out.println();
    }
}